"""
难度：简单
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
"""


"""
利用归并排序的思想。
创建一个新的链表节点作为头节点（记得保存），然后判断 l1和 l2 头节点的值，将较小值的节点添加到新的链表中。
当一个节点添加到新的链表中之后，将对应的 l1 或 l2 链表向后移动一位。
然后继续判断当前 l1 节点和当前 l2 节点的值，继续将较小值的节点添加到新的链表中，然后将对应的链表向后移动一位。
这样，当 l1 或 l2 遍历到最后，最多有一个链表还有节点未遍历，则直接将该节点链接到新的链表尾部即可。"""
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        newHead = ListNode(-1)
        curr = newHead
        while l1 and l2:
            if l1.val <l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next
        curr.next = l1 if l1 is not None else l2#当两个链表不相等的时候
       
        return newHead.next